// Created by WXX on 2021/11/2 15:02
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：12 ms, 在所有 C++ 提交中击败了65.45%的用户
 * 内存消耗：12.8 MB, 在所有 C++ 提交中击败了37.92%的用户
 */
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

        sort(arr2.begin(), arr2.end());
        int res = 0;
        for (int x : arr1) {
            int dist = 1e9;
            auto p = lower_bound(arr2.begin(), arr2.end(), x);
            if (p != arr2.end()) dist = min(dist, abs(x - *p));
            if (p != arr2.begin()) {
                --p;
                dist = min(dist, abs(x - *p));
            }
            if (dist > d) res++;
        }
        return res;
    }
};

int main() {

    vector<int> arr1 = {4, 5, 8};
    vector<int> arr2 = {10, 9, 1, 8};
    cout << Solution().findTheDistanceValue(arr1, arr2, 2) << endl;  // 2

    return 0;
}
